package sort;

/**
 * 冒泡
 * O(n^2)
 * 稳定的： 向后冒泡的时候，遇到和之间相等的不交换就能保证稳定性
 *
 * @author Liaorun
 */
public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        // 异或操作 ^ 相同为 0， 不同为 1
        // ^ 也可以理解为无进位相加
        // 10110 ^ 00111 = 10001
        // 1.  0 ^ N = N; N ^ N = 0;
        // 2.  异或运算 满足 交换率 和 结合率
        // a ^ b = b ^ a; (a ^b) ^ c = a ^ (b ^ c)
        // 3.
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }


}
